package com.example.tree.segmenttree;

/**
 * 线段树是一种平衡二叉搜索树(完全二叉树)，它将一个线段区间划分成一些单元区间。
 * 线段树一般包括建立、查询、插入、更新等操作，建立规模为N的时间复杂度是O(NlogN)，
 * 其他操作时间复杂度为O(logN) 。
 * 注意:一旦线段树构建完毕后，就不能再更改它的结构，但是可以对原数组的值进行修改，修改后整个线段树的结构不变
 * 节点值要对应发生变化
 * <p>
 * 当前实现的线段树：
 * 对的每一个非叶子节点，表示区间[a, b]的和(要根据不同的应用场景进行调整)，
 * 它的左孩子表示的区间为[a,(a+b)/2]，右孩子表示的区间为[(a+b)/2+1,b]，
 * 最后的叶子节点数目为N，与数组下标对应。
 */
public class SumSegmentTree {
    private int[] treeNodes; // 线段树数组,存储nums[left,right]的和(需要根据具体的用途进行调整)
    private int[] nums; // 处理数组
    private int n; // 处理数组的长度

    /**
     * @param nums 处理数组
     */
    public SumSegmentTree(int[] nums) {
        this.nums = nums;
        this.n = nums.length;
        this.treeNodes = new int[4 * this.n]; // n个叶子节点的完全二叉树最多有4*n个节点
        build(0, 0, n - 1);
    }

    /**
     * 构建线段树(递归)
     * 一旦构建完毕后线段树结构不再改变，但是可以进行修改和查询
     *
     * @param pos   线段树数组当前位置下标(nums[left,right]的和的下标)
     * @param left  处理区间下限(包含)
     * @param right 处理区间上限(包含)
     */
    private void build(int pos, int left, int right) {
        // 递归出口
        if (left == right) {
            treeNodes[pos] = nums[left];
            return;
        }
        int mid = (left + right) / 2;
        // 递归构建左右子树
        build(2 * pos + 1, left, mid);
        build(2 * pos + 2, mid + 1, right);

        treeNodes[pos] = treeNodes[2 * pos + 1] + treeNodes[2 * pos + 2];

    }

    /**
     * 线段树的求和
     * @param pos    线段树数组当前位置下标
     * @param left   处理区间下限(包含)
     * @param right  处理区间上限(包含)
     * @param qleft  求和区间下限(包含)
     * @param qright 求和区间上限(包含)
     * @return
     */
    public int query(int pos, int left, int right, int qleft, int qright) {
        // 递归出口
        if (qleft > right || qright < left) // 查询区间在当前区间之外
            return 0;
        if (qleft <= left && qright >= right) // 查询区间完全包含当前区间
            return treeNodes[pos];

        int mid = (left + right) / 2;

        int leftSum = query(2 * pos + 1, left, mid, qleft, qright);
        int rightSum = query(2 * pos + 2, mid + 1, right, qleft, qright);
        return leftSum + rightSum;

    }

    /**
     *
     * @param pos
     * @param left
     * @param right
     * @param index    要更新的数组元素的下标
     * @param newValue 要更新的数组元素的新值
     */
    public void update(int pos, int left, int right, int index, int newValue) {
        if (left == right && left == index) { // 叶子节点
            treeNodes[pos] = newValue;
            return;
        }
        int mid = (left + right) / 2;
        if (index <= mid) {
            update(2 * pos + 1, left, mid, index, newValue);
        } else {
            update(2 * pos + 2, mid + 1, right, index, newValue);
        }
        treeNodes[pos] = treeNodes[pos * 2 + 1] + treeNodes[pos * 2 + 2];

    }

    public static void main(String[] args) {
        int[] nums = {0, 1, 3, 4, 6};
        SumSegmentTree sumSegmentTree = new SumSegmentTree(nums);

//        for (int i = 0; i < sumSegmentTree.values.length; i++) {
//            System.out.println(sumSegmentTree.values[i]);
//        }

        // 调用线段树时pos要根据根节点的索引值来进行决定是传0(根节点下标为0时),还是传1(根节点下标为1)
        System.out.println(sumSegmentTree.query(0, 0, nums.length - 1, 0, 4));
        sumSegmentTree.update(0, 0, nums.length - 1, 2, 5);
        System.out.println(sumSegmentTree.query(0, 0, nums.length - 1, 0, 2));

    }
}
